package cn.nju.sirx.datastructure.collection;

/**
 * Bit set.
 * 
 * @author WangXiao
 */
public class BitSet {

    /**
     * Constructor.
     * 
     * @param length logical length of the bit set, that is the index of the
     *            highest set bit in the BitSet plus one.
     */
    public BitSet(int length) {
        if (length <= 0) {
            throw new IllegalArgumentException("size should be a positive number");
        }
        this.length = length;
        bytes = new byte[length % 8 == 0 ? length / 8 : length / 8 + 1];
    }

    /**
     * Get the logical length of the bit set, that is the index of the highest
     * set bit in the BitSet plus one.
     * 
     * @return logical length of the bit set
     */
    public int length() {
        return length;
    }
    
    /**
     * Get the size of the bit set, that is the elements count in bit set.
     * 
     * @return size of the bit set
     */
    public int size() {
        return size;
    }

    /**
     * Test whether the bit in a given position is 1.
     * 
     * @param offsetInSet a given position to test
     * @return true if the bit in given position is 1; false or else
     * @throws IndexOutOfBoundsException when offsetInSet < 0 or >= set size
     */
    public boolean test(int offsetInSet) {
        checkOutOfBounds(offsetInSet);
        
        int byteIndex = offsetInSet / 8;
        int offsetInByte = offsetInSet % 8;
        return (bytes[byteIndex] & 1 << (7 - offsetInByte)) != 0;
    }
    
    /**
     * Set the bit in a given position to 1.
     * 
     * @param offsetInSet a given position to set
     * @throws IndexOutOfBoundsException when offsetInSet < 0 or >= set size
     */
    public void set(int offsetInSet) {
        checkOutOfBounds(offsetInSet);

        int byteIndex = offsetInSet / 8;
        int offsetInByte = offsetInSet % 8;
        if ((bytes[byteIndex] & 1 << (7 - offsetInByte)) == 0) {
            bytes[byteIndex] |= 1 << (7 - offsetInByte);
            size++;
        }
    }

    /**
     * Set the bit in a given position to 0.
     * 
     * @param offsetInSet a given position to set
     * @throws IndexOutOfBoundsException when offsetInSet < 0 or >= set size
     */
    public void clear(int offsetInSet) {
        checkOutOfBounds(offsetInSet);

        int byteIndex = offsetInSet / 8;
        int offsetInByte = offsetInSet % 8;
        if ((bytes[byteIndex] & 1 << (7 - offsetInByte)) != 0) {
            bytes[byteIndex] &= ~(1 << (7 - offsetInByte));
            size--;
        }
    }

    /**
     * Get the string with hex format of the set bits.
     * 
     * @return the string with hex format of the set bits, like
     *         "84000000000000000000000008".
     */
    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer(bytes.length * 8);
        for (int i = 0; i < bytes.length; i++) {
            String formatted = String.format("%x", bytes[i]);
            if (formatted.length() == 1) {
                buffer.append('0');
            }
            buffer.append(formatted);
        }
        return buffer.toString();
    }

    private void checkOutOfBounds(int offsetInSet) {
        if (offsetInSet < 0 || offsetInSet >= length) {
            throw new IndexOutOfBoundsException(offsetInSet + " out of bounds "
                    + length);
        }
    }

    private int length; // logical length of bit set
    private int size; // elements count in bit set
    private byte[] bytes; // an array of bytes
}
